package com.tuhailong.algorithm;

public class StringSearch {

	private static final boolean DEBUG = true;

	// private static final String SRC = "https://github.com/tuhailong/algorithm";
	// private static final String DST = "github";

	private static final String SRC = "abababaababacb";
	private static final String DST = "ababacb";

	private static void printArray(int list[]) {
		int len = list.length;
		System.out.print("[");
		for (int i = 0; i < len; ++i) {
			System.out.print(list[i]);
			if (i != len - 1) {
				System.out.print(", ");
			}
		}
		System.out.println("]");
	}

	private static int[] getNext(char ch[]) {
		int len = ch.length;
		int next[] = new int[len];

		next[0] = -1;
		int i = 0;
		int j = -1;

		while (i < len - 1) {
			if (j == -1 || ch[i] == ch[j]) {
				++i;
				++j;
				if (ch[i] != ch[j]) {
					next[i] = j;
				} else {
					next[i] = next[j];
				}
			} else {
				j = next[j];
			}
		}

		return next;
	}

	// K.M.P. Search
	public static int kmpSearch(char[] src, char[] dst) {
		int srcLen = src.length;
		int dstLen = dst.length;

		if (srcLen < dstLen) {
			return -1;
		}

		int[] next = getNext(dst);

		if (DEBUG) {
			System.out.print("kmpSearch: next[" + next.length + "]=");
			printArray(next);
		}

		int i = 0;
		int j = 0;

		while (i <= srcLen - 1 && j <= dstLen - 1) {
			if (j == -1 || src[i] == dst[j]) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}

		if (j < dstLen) {
			return -1;
		} else {
			// return the first index position
			return i - dstLen;
		}
	}

	// Brute Force Search
	public static int bfSearch(String source, String pattern) {
		int slen = source.length();
		int plen = pattern.length();

		if (slen < plen) {
			return -1;
		}

		char sch[] = source.toCharArray();
		char pch[] = pattern.toCharArray();

		// 'i' stands for the index of source string
		for (int i = 0; i < slen; ++i) {
			int j;
			// 'j' stands for the index of pattern string
			for (j = 0; j < plen; ++j) {
				// 'index' stands for the index of source string
				int index = i + j;
				if (index >= slen) {
					return -1;
				}
				if (sch[index] != pch[j]) {
					j = 0;
					break;
				}
			}
			// when 'j' reached the value of pattern string length,
			// pattern string is flagrantly in source string
			if (plen == j) {
				return i;
			}
		}

		return -1;
	}

	public static void main(String[] args) {
		char src[] = SRC.toCharArray();
		char dst[] = DST.toCharArray();

		int index = kmpSearch(src, dst);
		if (index < 0) {
			System.out.println("kmpSearch: " + DST + " is not in " + SRC);
		} else {
			System.out.println("kmpSearch: " + DST + " is in " + SRC + ": index=" + index);
		}

		index = bfSearch(SRC, DST);
		if (index < 0) {
			System.out.println("bfSearch: " + DST + " is not in " + SRC);
		} else {
			System.out.println("bfSearch: " + DST + " is in " + SRC + ": index=" + index);
		}
	}

}
